\section{Related Work}

Work related to this paper falls into two main categories; (1)
automated approaches to localize software bugs; and (2) Markov
logic network and its applications.

\subsection{Automated Software Bug Localization}

Interest in automated software bug localization has grown rapidly in recent years,
and many approaches have been proposed. For example, the Nearest Neighbor (NN)~\cite{reiss:2003}
approach first selects a single failed program execution, and computes the passed execution that
has the most similar statement coverage. Then it creates the set of all statements
that are covered in the failed execution but not in the passed execution.
The Cause Transition (CT)~\cite{Cleve:2005}
approach compares the program states of a failing and a passing execution, and actively
searches for failure-inducing circumstances in the differences between these states.
Other dynamic approaches such as dynamic slicing~\cite{Zhang:2003} narrows down
the search space to the set of statements that may influence a value at a program
location where the bug occurs (e.g., an incorrect output value is observed). 
\textsc{Tarantula}~\cite{Jones02visualizationof}, a statement coverage-based bug localization technique,
utilizes information obtained from both passing/failing tests
to identify buggy statements under the assumption that
that statements covered by more failing tests are more likely to be buggy. In
a comprehensive comparison study~\cite{Jones:2005}, Tarantula
consistently outperforms
other approaches and thus is the \textit{most} effective one been compared. However,
these existing techniques tend to use isolated information
(e.g., statement coverage information in Tarantula~\cite{Jones02visualizationof}, or
static program structure in CT~\cite{Cleve:2005}) to localize the bugs. 
%while
%ignoring the crosstalk between different information sources.
In contrast,
our approach uses Markov logic to combine multiple different
information sources to localize potential bugs via joint inference. As
indicated by our experiments, this Markov logic-based approach
substantially outperforms Tarantula in terms of bug localization accuracy
on the same programs.

%However, in contrast to previous approaches, our approach xxxxx; hence.  xxx In particular, xxx

Several other researchers are studying the software bug localization problem
from different perspectives. Instead of determining buggy \textit{statements}, their
approaches aim to identify likely buggy \textit{program predicates}. For example,
Liblit et al.~\cite{Liblit:2005}
proposed a statistical algorithm which used sampling to collect data
in deployed programs and identified
predicates which are relevant to bugs. Jiang and Su~\cite{Jiang:2007} proposed
an approach to automatically
generate a faulty control flow path by clustering correlated predicates. The faulty flow path
can help users to understand the bug but cannot provide the exact buggy locations.
Chilimbi et al.~\cite{Chilimbi:2009} 
presented a debugging tool called \textsc{HOLMES} that used path profiles instead of
predicate profiles to isolate bugs.


Significantly differing from the existing work that statistically infers the distributions for buggy
predicates or path profiles, our approach uses Markov logic to build a general model for each program
statement and then uses the built model to reason about the observed buggy behaviors.
Furthermore, our approach
permits to seamlessly combine many different information sources (e.g., different program features)
 into a comprehension solution to the bug localization problems, avoiding using isolated
information.

%our approach
%uses MLN inference techniques to overcome the limitation of existing Bayesian network inference
%technique to identify the bug location.


%A related problem is XXXX. XXX is one way to solve it, however, its model xxxxx lies in xxx,
%and the states are XXX.

%Several researchers are studying xxx from different perspectives. Ensuring xxx correctness is
%one essential challenge in xxx.  XXX observe that,  but xxx.


% Among a rich body of existing
%testing-based bug localization techniques~\cite{Wang:2009, Santelices:2009, Wong:2007,Zhang:2009,Abreu:2007}, perhaps, the most closely
%related works to our project are those that perform bug localization using probabilistic program
%behavior models. The work of Feng and Gupta~\cite{feng:learning} uses the standard Bayesian network inference
%techniques to predict the buggy statements. Liu et al~\cite{soberliu05} and Baah et al~\cite{baah08jul} applied probabilistic models to
%analyze the behavior of predicates in passing and failing runs. Their method builds a distribution
%for the outcomes of each predicate in both passing runs and failing runs and locates the fault by
%comparing the distributions in passing runs with those in failing runs. They suggest if the
%behavior of a predicate in a failing run is significantly different from that in passing run,
%it is probably relevant to the failure.



%Finally, our work is related to the growing body of work in xxxx


\subsection{Markov Logic Network and its Applications}

As a powerful representation for joint inference with uncertainty, Markov logic~\cite{Richardson06markovlogic}
%provides a probabilistic extension of first-order logic and makes it possible
%to compactly specify probability distribution over complex relational domains.
%It
has been widely used in many application domains, such as natural language processing~\cite{Poon:2009:UMS},
entity resolution~\cite{Singla:2006},
hypertext classification~\cite{Chakrabarti:1998}, information extraction~\cite{Poon:2007},
and semantic processing~\cite{poon2009}.
However, the software bug localization problem addressed in this paper is
 significantly different from what previous research focused on.
Within our best knowledge, we are the \textit{first} to apply Markov logic to the domain of software bug
localization, and demonstrate its effectiveness through experiments on real-world programs.

